package com.javaDemo.ti;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @ClassName: Zuichangbuchongfu
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
 * @Auther: csy
 * @Date: 2020/6/7 23:22
 * @Description:
 */
public class Zuichangbuchongfu {

    // public static int lengthOfLongestSubstring(String s) {
    //     // 哈希集合，记录每个字符是否出现过
    //     Set<Character> occ = new HashSet<Character>();
    //     int n = s.length();
    //     // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    //     int rk = 0, ans = 0;
    //     for (int i = 0; i < n; ++i) {
    //         if (i != 0) {
    //             // 左指针向右移动一格，移除一个字符
    //             occ.remove(s.charAt(i - 1));
    //         }
    //         while (rk  < n && !occ.contains(s.charAt(rk ))) {
    //             // 不断地移动右指针
    //             occ.add(s.charAt(rk ));
    //             ++rk;
    //         }
    //         // 第 i 到 rk 个字符是一个极长的无重复字符子串
    //         ans = Math.max(ans, rk - i );
    //     }
    //     return ans;
    // }


    public static int solution1(String a) {
        int len = a.length();
        int result = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int s = 0, e = 0; e < len; e++) {
            char ec = a.charAt(e);
            if (map.containsKey(ec)) {
                s = Math.max(map.get(ec), s);
            }
            result = Math.max(result, e - s + 1);
            map.put(a.charAt(e), e + 1);
        }
        return result;
    }

    public static int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }

    static String result = "";
    static Integer count = 0;

    //修改获取最长子串
    public static void main(String[] args) {
        String a = "abacdeac";
        // System.out.println(Solution.lengthOfLongestSubstring(a));
        // getChildStr(a);
        // System.out.println(result);

        solution1(a);
        System.out.println(result);

        // getMaxsubHuisu(a);
    }

    public static void getChildStr(String a) {
        if (a.length() == 1) {
            result = a;
        }
        int length = a.length();
        Queue<Character> queue = new LinkedList<>();
        int start = 0, end = 0;
        while (end < length) {
            if (queue.contains(a.charAt(end))) {
                queue.clear();
                result = a.substring(start, end);
                // if (count < end - start) {
                //     count = 0;
                // } else {
                //     count = end - start;
                // }
                start = start+1;
            }
            queue.add(a.charAt(end));
            end++;
        }
    }

    public static String getMaxsubHuisu(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }

        int start = 0;//滑动窗口的开始值
        int maxlen = 0;
        int len = 0;
        int startMaxIndex = 0;//最长子串的开始值
        Map<Character, Integer> map = new HashMap<>();//存储窗口内字符跟位置
        int i;
        for (i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            Integer value = map.get(ch);
            if (map.containsKey(ch)) {//map中包含字符，则出现重复字符
                start = value + 1;//下一次开始的位置是，存在map中重复字符的下一个位置
                len = 0;//重新开始新的窗口，len置为0
                map = new HashMap<>();//map置空
                i = value;//下次从重复的值开始回溯
            } else {
                map.put(ch, i);//不存在重复的，就存入map
                len++;//每次进来长度自增1
                if (len > maxlen) {//如果当前的窗口长度>最长字符串则，更新最长串，跟最长子串开始位置
                    maxlen = len;
                    startMaxIndex = start;
                }
            }
        }
        return s.substring(startMaxIndex, (startMaxIndex + maxlen));//截取字符串，substring为左闭右开
    }
}